package leetcode_top;
import org.junit.Test;

import linked.*;
public class Ex25 {
    /**
     * Definition for singly-linked list. public class ListNode { int val; ListNode
     * next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val,
     * ListNode next) { this.val = val; this.next = next; } }
     */
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (k <= 1)
                return head;
            ListNode end = head, cur = head, tmp, res = null;
            int t = k;
            while (cur != null) {
                res = cur;
                cur = cur.next;
                t--;
                if (t == 0) {
                    break;
                }
            }
            cur = head;
            tmp = null;
            while (cur != null) {
                end = findEnd(cur, k);
                if (end == cur) {
                    // 不足k个
                    break;
                }
                ListNode next = reverse(cur, end);
                if (tmp != null)
                    tmp.next = next;
                tmp = cur;
                cur = end;
            }
            return res;
        }

        // 规定返回首节点表示不足k个
        public ListNode findEnd(ListNode head, int k) {
            ListNode cur = head;
            while (cur != null) {
                k--;
                cur = cur.next;
                if (k == 0) {
                    break;
                }
            }
            return k == 0 ? cur : head;
        }

        public ListNode reverse(ListNode head, ListNode end) {
            ListNode pre = end, post = head, tmp;
            while (post != end) {
                tmp = post.next;
                post.next = pre;
                pre = post;
                post = tmp;
            }
            return pre;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.reverseKGroup(ListNode.newListNodeFromArray(new int[]{1,2,3,4,5}), 3));        
    }
}
